Queues

Introduction

A queue is an abstract data structure that contains a collection of elements. Queue implements the FIFO mechanism i.e. the element that is pushed at the front is popped out first. Some of the principle operations in the stack are −

Enqueue - This adds a data value to the back of the queue

Dequeue - This removes the data value from the front of the queue

Complexities

Time Complexity

Write

O(1)

Access

O(1)

Implementation

Go with Linked List

type Node struct{
    data interface{}
    next *Node
}

func NewNode(d interface{}) *Node{
    return &Node{
        d,
        nil,
    }
}

type Queue struct{
    head *Node
    tail *Node
    count int
}

func (q *Queue) New() *Queue{
    return &Queue{
        nil,
        nil,
        0,
    }
}

func (q *Queue) size() int{
    return q.count
}

func (q *Queue) enqueue(d interface{}){
    n := NewNode(d)
    if q.head == nil{
        q.head = n
    }else{
        q.tail.next = n
    }
    q.count ++
    q.tail = n
}

func (q *Queue) dequeue() interface{}{
    if q.head == nil{
        return nil
    }

    n := q.head
    q.head = q.head.next

    if q.head == nil{
        q.tail = nil
    }
    q.count--
    return n.data
}

func (q *Queue) front() interface{}{
    return q.head
}

func (q *Queue) back() interface{}{
    return q.tail
}

func main() {
    var q Queue
    queue := q.New()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    fmt.Println("Front:", queue.front())
    fmt.Println("Back:", queue.back())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Front:", queue.front())
    fmt.Println("Back:", queue.back())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
}

Go with Slice

type Queue []interface{}

func (q *Queue) size() int{
    return len(*q)
}

func (q *Queue) enqueue(d interface{}){
    *q = append(*q,d)
}

func (q *Queue) dequeue() interface{}{
    if len(*q) == 0{
        return nil
    }
    head := (*q)[0]
    *q = (*q)[1:]
    return head
}

func (q *Queue) front() interface{}{
    return (*q)[0]
}

func (q *Queue) back() interface{}{
    index := len(*q)-1
    return (*q)[index]
}

func main() {
    var queue Queue
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    fmt.Println("Front:", queue.front())
    fmt.Println("Back:", queue.back())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Front:", queue.front())
    fmt.Println("Back:", queue.back())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
    fmt.Println(queue.dequeue())
    fmt.Println("Size:", queue.size())
}